package 树与图.字典树;

import java.util.Stack;

/**
 * 100. 相同的树
 *
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 *
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 *
 * 思路：
 *  要判断两棵树是否相同，我们需要比较它的结构与每个节点的值，具体步骤如下:
 *  1:递归比较：
 *      如果两个树都为空，则它们相同。
 *      如果一个树为空，另一个不为空，则它们不相同。
 *      如果两个树的根节点值不同，则它们不相同。
 *      递归比较左子树和右子树；
 *  2:终止条件：
 *      当两个树都为空时，返回true；
 *      当一个树为空，另一个不为空时，返回false
 */
public class L_100 {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 递归终止条件：当两个树都为空时，返回true；
        if(p == null && q == null){
            return true;
        }
        // 如果一个树为空，另一个树不为空
        if(p == null || q == null){
            return false;
        }
        // 如果两个树的根节点值不同，则返回false
        if(p.val != q.val){
            return false;
        }
        // 递归比较左子树和右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public boolean isSameTree1(TreeNode p, TreeNode q) {
        // 使用栈来模拟递归
        Stack<TreeNode[]> stack = new Stack<>();
        stack.push(new TreeNode[]{p, q}); // 将根节点对压入栈

        while (!stack.isEmpty()) {
            TreeNode[] nodes = stack.pop();
            TreeNode node1 = nodes[0];
            TreeNode node2 = nodes[1];

            // 如果两个节点都为空，继续检查下一个节点
            if (node1 == null && node2 == null) {
                continue;
            }
            // 如果一个节点为空，另一个不为空，返回false
            if (node1 == null || node2 == null) {
                return false;
            }
            // 如果节点值不相同，返回false
            if (node1.val != node2.val) {
                return false;
            }

            // 将左子节点对和右子节点对压入栈
            stack.push(new TreeNode[]{node1.left, node2.left});
            stack.push(new TreeNode[]{node1.right, node2.right});
        }

        // 如果栈为空，说明所有节点都匹配
        return true;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
